package leetcodecompetition.D355;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @Author: Siantar
 * @Date: 2023-07-23-11:00
 * @Description: 1.0
 */
public class T6955 {
    public int maxIncreasingGroups(List<Integer> usageLimits) {
        int n = usageLimits.size();
        int[] arr = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = usageLimits.get(i);
            if(arr[i]>=n) arr[i] = n;

        }
        Arrays.sort(arr);
        long[] pre = new long[n+1];
        for(int i=0;i<n;i++) {
            pre[i+1] = pre[i] + arr[i];
        }
        int l=1,r=n;
        if(check(n,arr,pre)) return n;
        while(l<r) {
            int m = l+(r-l+1)/2;
            if(check(m,arr,pre)) {
                l = m;
            } else {
                r = m-1;
            }
        }
        return l;
    }
    boolean check(int v,int[] arr,long[] pre) {
        int n = arr.length;
        int i=0;
        while(i<v && arr[n-i-1]>=v-i) i++;
        // System.out.println(String.format("%s %s %d %d",Arrays.toString(arr),Arrays.toString(pre),v,i));
        if(i==v) return true;
        // long t = v-i;
        // t = t * (t+1)/2;
        // if(pre[n-i]<t) return false;
        for(int j=0;j<v;j++) if(pre[n-v+j+1]<(long)(j+1)*(j+2)/2) return false;
        return true;
    }

}
